/*
 * @lc app=leetcode.cn id=1036 lang=typescript
 *
 * [1036] 逃离大迷宫
 */

// @lc code=start
function isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const N = 1e6;
  // 广度优先遍历的最大次数
  const M = blocked.length;
  const MAX = (M * (M - 1)) / 2;
  // block哈希表
  const blockedSet = new Set(blocked.map(([x, y]) => `${x},${y}`));

  const isValid = (s: number[], t: number[]) => {
    const visited: Set<string> = new Set();
    const queue: number[][] = [s];

    while (queue.length && visited.size <= MAX) {
      const [x, y] = queue.shift();
      if (x === t[0] && y === t[1]) return true;
      for (const [dx, dy] of directions) {
        const nextX = x + dx;
        const nextY = y + dy;
        if (nextX < 0 || nextX >= N) continue;
        if (nextY < 0 || nextY >= N) continue;
        if (blockedSet.has(`${nextX},${nextY}`)) continue;
        if (visited.has(`${nextX},${nextY}`)) continue;
        visited.add(`${nextX},${nextY}`);
        queue.push([nextX, nextY]);
      }
    }

    return visited.size > MAX;
  };

  // 判断是否可以从source到target
  // 判断是否可以从target到source
  return isValid(source, target) && isValid(target, source);
}
// @lc code=end
